并查集深度实战：从等价划分、路径压缩到按秩合并与可撤销/持久化的工程全解
系统拆解并查集（Disjoint Set Union）的第一性原理：用有根森林表示等价类划分，find/union 如何把"是否连通"转化为"根是否相同"。从朴素实现的 O(n) 退化陷阱出发，推导两大核心优化——路径压缩（迭代版，规避 Python 递归爆栈）与按秩/按大小合并——二者叠加把摊还复杂度钉死在反阿克曼函数 α(n)（物理可观测尺度内 α(n)≤4，近似常数）。进而展开变体谱系：加权/种类并查集、可撤销并查集（仅按大小合并+栈回滚，禁用路径压缩）、持久化并查集、DSU on tree、离线动态连通性、网格并查集。给出 Kruskal MST/连通分量/图像分割/等式约束/类型合一 等应用对照表、12 项生产陷阱清单（递归压缩爆栈、索引混淆、可撤销误用压缩等）与可复现 Python 工具箱。与本站 布隆过滤器/Count-Min Sketch/HyperLogLog/布谷鸟哈希 共同构成"概率与高性能数据结构工程"系列，前者提供确定性精确的等价类划分，后者提供概率近似的集合成员/频率/基数估计，工程栈中互补共存。
